내시 균형

3. 정의

내시 균형은 게임 이론에서 중요한 개념으로, 모든 플레이어가 상대방의 전략을 알고 있고, 그 전제 하에 자신의 최적 전략을 선택했을 때, 어느 누구도 일방적으로 전략을 바꿔서 더 이득을 볼 수 없는 상태를 말한다.
비공식적 정의:쉽게 말하면, 각 플레이어가 다른 플레이어들의 전략을 알고 있다고 가정했을 때, "내가 전략을 바꾸면 더 이득을 볼 수 있을까?"라고 스스로에게 질문했을 때, "아니오"라고 답할 수 있는 상태가 내시 균형이다.^[16] 즉, 모든 플레이어가 현재 전략에 만족하고 굳이 바꿀 필요성을 느끼지 못하는 상황이다.
공식적 정의:조금 더 수학적으로 표현하면 다음과 같다.

• $n$명의 플레이어가 있는 게임에서, 각 플레이어 $i$는 전략 집합 $S\_i$에서 전략 $x\_i$를 선택한다.
• 모든 플레이어의 전략 조합을 $x\; =\; (x\_1,\; \backslash dotsc,\; x\_n)$라고 하고, 이익 함수를 $f=(f\_1(x),\; \backslash dotsc,\; f\_n(x))$라고 한다.
• $x\_\{-i\}$는 플레이어 $i$를 제외한 나머지 플레이어들의 전략 조합을 의미한다.

• 내시 균형은 모든 플레이어가 상대방의 전략을 전제로 최적의 전략을 선택한 결과이다.
• 어느 누구도 일방적으로 전략을 변경하여 이득을 얻을 수 없다.^[16]
• 내시 균형은 때때로 파레토 최적이 아닐 수 있으며, 비이성적인 결과를 낳을 수도 있다.

3. 1. 순수 전략 내시 균형

먼저 P_a의 이득에 주목하면, P_b가 어떤 전략을 선택하든, P_a는 A₁ 전략을 선택하는 것이 더 큰 이득을 얻을 수 있다. 이러한 관계가 성립할 때, A₁은 강지배 전략이라고 표현한다. '''지배'''한다는 것은 어떤 전략을 선택하는 것이 다른 전략을 선택하는 것보다 유리하다는 의미이다.

다음으로 P_b의 이득에 주목하면, P_a가 어떤 전략을 선택하든, B₂ 전략을 선택하는 것이 B₁ 전략보다 더 큰 이득을 얻을 수 있다. P_a가 A₂ 전략을 선택한 경우에는 B₁과 B₂는 동등해지므로, 이러한 관계일 때 B₂는 약지배 전략이라고 한다.

결과적으로, P_a에게 최적 전략은 A₁, P_b에게 최적 전략은 B₂가 되며, 둘 다 여기서 전략을 변경해도 이득은 감소한다. 이 조합 (A₁, B₂)가 '''지배 전략 균형'''이 된다.

P_a, P_b가 (A₁, B₂)라는 전략을 선택한 경우, P_a는 전략을 변경하여 A₂를 선택하면 이득이 2에서 1로 감소하므로, 전략을 변경할 유인이 없다. 마찬가지로 P_b도 전략을 변경하여 B₁을 선택하면 이득이 4에서 2로 감소하므로, 전략을 변경할 유인이 없다. 따라서 이 예에서 지배 전략 균형은 내시 균형이다.

한편, P_a, P_b가 (A₂, B₁)이라는 전략을 선택했을 때의 이득은 (4, 6)이 되며, 내시 균형에서의 이득과 비교하여 P_a, P_b 모두 더 큰 이득을 얻을 수 있다. 이 경우, P_a가 더 큰 5의 이득을 얻기 위해 A₁으로 전략을 변경할 유인을 가지므로, 내시 균형이 아니다. 즉, 이 게임은 죄수의 딜레마 게임이다. 또한, (A₁, B₂)에서 (A₂, B₁)으로의 전략 변경은 파레토 개선이며, 내시 균형 (A₁, B₂)은 파레토 효율적이지 않다.

상대방의 전략에 따라 어떤 전략이 가장 큰 이득을 내는지가 변하는 경우, 다른 모든 전략을 지배할 수 있는 전략이 존재하지 않을 수 있다. 그러한 경우, 다른 전략에 의해 지배되는 전략(피지배 전략)을 제거해 나감으로써 남은 전략의 조합을 지배 전략 균형으로 정의할 수 있다. 지배 전략에 의해 내시 균형이 정의될 수 있는 경우, 이는 제거에 의해 정의된 것과 일치한다.

B₃는 B₂에 의해 지배되므로, B₃를 제거한다.

A₃는 A₂에 의해 지배되므로 A₃를 제거한다.

B₁은 B₂에 의해 지배되므로 B₁을 제거한다.

지배 전략 균형은 (A₂, B₂)이다.

다른 플레이어의 전략에 관계없이 최대 이익을 가져다주는 전략의 조합(지배 전략 균형)과 지배 전략의 순차적 소거를 통해 얻을 수 있는 전략의 조합은 같지만, 게임 설정에 따라 앞서 언급한 두 가지 방법으로는 균형을 구할 수 없는 경우가 있다. 내시 균형의 정의에 따르면 다른 플레이어의 전략을 '''최적 반응'''이라고 가정하고 자신의 최적 반응을 구하면 되므로, 지배 전략 균형이 존재하지 않는 순수 전략 게임에서도 내시 균형을 찾을 수 있다.

예를 들어 위의 3×3 표준형 게임의 (A₁, B₃)의 이익을 (4, 0)에서 (4, 5)로 변경하면 어떤 전략도 순차적으로 소거되지 않아 지배 전략 균형을 구할 수 없다.

하지만 상대의 전략을 주어진 것으로 가정했을 때 최대 이익을 가져다주는 전략(최적 반응)을 조합해 가면, 유일하게 (A₂, B₂)가 최적 반응의 조합이 된다는 것을 알 수 있다. 따라서 이 게임에는 '''순수 전략 내시 균형'''이 한 쌍 존재한다.

3. 2. 혼합 전략 내시 균형

A가 H를 낼 확률을 $p$, T를 낼 확률을 $(1-p)$로, B가 H를 낼 확률을 $q$, T를 낼 확률을 $(1-q)$로 지정하면, 각 플레이어의 기대 보수를 계산하여 $p\; =\; \backslash frac\{1\}\{2\}$, $q\; =\; \backslash frac\{1\}\{2\}$라는 혼합 전략 내시 균형을 얻을 수 있다.^[16]

혼합 전략 게임은 참가자가 행동을 확률적으로 선택하여 내시 균형에 도달하는 비협력 게임이다. 이러한 게임에서는 순수 전략 내시 균형이 반드시 존재하지 않을 수 있으며, 내시 균형은 각 참가자의 행동 확률 조합으로 표시된다.

4. 내시 균형의 유형

어떤 플레이어도 자신의 전략을 일방적으로 변경하여 더 나은 결과를 얻을 수 없을 때의 전략 프로파일을 내시 균형이라고 한다. 모든 플레이어가 변경하지 않기를 선호하거나 변경 여부에 대해 무관심하다면 해당 전략 프로파일은 내시 균형이 된다.^[16]

내시 균형은 다음과 같이 분류할 수 있다.

• 엄격한 내시 균형 (Strict Nash Equilibrium): 모든 플레이어의 답변이 "그렇다"인 경우, 즉 모든 플레이어가 현재 전략을 유지하는 것이 최선인 경우이다.^[17]

• 약한 내시 균형 (Weak Nash Equilibrium): 어떤 플레이어에게는 현재 전략과 동일한 보상을 주는 다른 전략이 존재하는 경우, 즉 플레이어가 전략 변경에 무관심한 경우이다.

• 강한 내시 균형 (Strong Nash Equilibrium): 모든 가능한 연합의 이탈을 허용한다.^[18] 형식적으로, 강한 내시 균형은 보완 연합의 행동을 주어진 것으로 간주하여 어떤 연합도 구성원 모두에게 이익이 되는 방식으로 협력적으로 이탈할 수 없는 내시 균형이다.^[19]
• 연합 방지 내시 균형 (CPNE)^[18]: 참여자들이 소통하고 "자체 시행" 합의를 통해 이탈할 수 있도록 허용하더라도 더 나은 결과를 얻을 수 없을 때 발생한다.
• 부분 게임 완전 내시 균형 (Subgame Perfect Nash Equilibrium): 내시 균형 외에도 해당 게임의 모든 부분 게임에서 해당 전략이 내시 균형을 이루도록 요구한다. 이는 모든 비현실적 위협을 제거한다.

• 혼합 전략 내시 균형 (Mixed Strategy Nash Equilibrium): 혼합 전략 게임이란, 참가자가 행동을 확률적으로 선택하는 전략을 취함으로써 내시 균형에 도달하는 비협력 게임을 말한다.

이 게임에서 각 플레이어의 최적 반응을 그래프로 나타내면(균형 경로), 혼합 전략 내시 균형은 균형 경로의 교차점이 된다. 따라서 혼합 전략 내시 균형에서 P_a는 (1/3, 2/3)을 선택하고, P_b는 (2/3, 1/3)을 선택한다. 이러한 형태의 게임은 양성의 싸움이라고 불린다.

5. 응용

내시 균형은 현실의 다양한 분야에 적용되어, 복잡한 의사 결정 상황을 분석하고 예측하는 데 도움을 준다.

• '''경제:''' 과점 시장에서의 기업 간 경쟁, 경매 방식 설계, 협상 전략, 공공재 공급, 환경 규제, 국제 무역 협정 등 다양한 경제 현상을 분석하는 데 활용된다. 예를 들어, 오귀스탱 쿠르노는 1838년 과점 이론에서 기업들이 이윤을 극대화하기 위해 생산량을 결정할 때 내시 균형 개념을 사용했다.^[13] 각 기업의 최적 생산량은 다른 기업의 생산량에 영향을 받으며, 이러한 상호 의존성을 고려하여 균형점을 찾는다.
• '''정치:''' 선거, 정당 간 경쟁, 정책 결정, 국제 관계, 군비 경쟁 등 정치적 상황을 분석하는 데 사용된다. 특히, 적대적인 상황에서 전쟁이나 군비 경쟁(죄수의 딜레마)을 분석하고, 반복적인 상호작용을 통해 갈등을 완화하는 방안을 모색하는 데 유용하다.
• '''사회:''' 교통 체증, 네트워크, 사회적 규범 형성, 젠더 갈등 등 사회 현상을 이해하는 데 도움을 준다. 예를 들어, 교통 흐름(워드롭의 원리)을 분석하여 최적의 교통 시스템을 설계하거나, 사회적 협력의 중요성을 강조하는 사슴 사냥 게임을 통해 협력의 가치를 설명할 수 있다.
• '''스포츠:''' 축구의 승부차기, 경기 전략 등 스포츠 경기에서 나타나는 전략적 상호작용을 분석하는 데 활용된다.
• '''기타:''' 생물학, 컴퓨터 과학, 인공지능, 군중 속의 로봇 내비게이션, 에너지 시스템, 운송 시스템, 대피 문제, 무선 통신 등 다양한 분야에 적용된다.

• '''조정 게임''': 두 명의 플레이어가 서로 다른 전략을 선택할 때, 두 플레이어 모두에게 최선의 결과가 나오는 균형이 존재하는 게임이다. 예를 들어, 운전할 때 도로의 왼쪽이나 오른쪽 중 하나를 선택하는 상황이 이에 해당한다. 양쪽 운전자가 모두 왼쪽 또는 오른쪽으로 운전하는 경우 두 개의 순수 전략 내시 균형이 존재한다.

• '''사슴 사냥 게임''': 사회적 협력의 중요성을 보여주는 게임으로, 두 명의 사냥꾼이 사슴 사냥과 토끼 사냥 중 하나를 선택하는 상황을 가정한다. 사슴 사냥은 더 큰 보상을 제공하지만, 두 사냥꾼이 협력해야만 성공할 수 있다. 반면, 토끼 사냥은 혼자서도 가능하지만 보상이 적다. 이 게임에는 (사슴, 사슴)과 (토끼, 토끼) 두 개의 내시 균형이 존재한다.

• '''경쟁 게임''': 두 명의 플레이어가 동시에 숫자를 선택하고, 더 작은 숫자를 선택한 플레이어가 점수를 얻는 게임이다. 만약 한 플레이어가 다른 플레이어보다 큰 숫자를 선택하면 상대방에게 2점을 줘야 한다. 이 게임은 (0, 0)이라는 유일한 순수 전략 내시 균형을 갖는다.

6. 한국 사회에의 적용 및 중도진보적 관점

내시 균형 개념은 한국의 정치, 경제, 사회 현상을 분석하는 데 유용하게 사용될 수 있다.

강한 내시 균형은 모든 가능한 연합의 이탈을 허용하는 개념이다.^[18] 이는 구성원 모두에게 이익이 되는 방식으로 협력적 이탈이 불가능한 내시 균형을 의미한다.^[19] 그러나 무제한적 사적 의사소통을 허용한다는 점에서 너무 "강하다"는 평가를 받기도 하며, 파레토 효율성을 가져야 한다는 조건 때문에 게임 이론에서 유용하게 쓰이기 어렵다.

연합 방지 내시 균형(CPNE)은 참여자들이 소통과 자체 시행 합의를 통해 이탈을 허용해도 더 나은 결과를 얻을 수 없을 때 발생한다.^[18] 이는 반복적인 엄격한 우월성에 의해 지원되고 파레토 경계에 있는 모든 상관된 전략이 해당된다.^[20] CPNE는 코어 이론과 관련이 있다.

6. 1. 정치

6. 2. 경제

• 두 명의 플레이어가 동시에 숫자를 지정하고 더 큰 숫자를 지정한 플레이어가 승리하는 게임은 선택 집합이 무제한이므로 콤팩트하지 않아 Nash equilibrium^영어을 갖지 않는다.
• 두 플레이어는 각각 5보다 엄격하게 작은 실수를 선택하고 승자는 가장 큰 숫자를 가진 사람이 된다. 5보다 엄격하게 작은 가장 큰 숫자는 존재하지 않는다 (숫자가 5와 같을 수 있다면 Nash equilibrium^영어은 두 플레이어가 5를 선택하고 게임을 비기는 것이다). 여기서 선택 집합은 닫혀 있지 않기 때문에 콤팩트하지 않다.

6. 3. 사회

7. 한계 및 비판

내시 균형은 현실을 단순화하여 설명하기 때문에 한계가 있다. 인간의 비합리성, 정보의 불완전성, 그리고 외부 효과 등을 제대로 고려하지 못하는 경우가 있다.

예를 들어, 어떤 플레이어가 "예"를 선호한다면, 해당 전략 집합은 내시 균형이 아니다. 그러나 모든 플레이어가 전략 변경을 원하지 않거나 변경에 무관심하다면 그 전략 프로파일은 내시 균형이 된다. 즉, 내시 균형의 각 전략은 해당 균형에서 다른 플레이어들의 전략에 대한 최적 반응이다.^[16]

내시 균형은 개별 참여자의 이탈에 대해서만 안정성을 정의하기 때문에, 협동 게임에서는 충분히 설득력 있는 개념이 아니다. 강한 내시 균형은 모든 가능한 연합의 이탈을 허용한다.^[18] 강한 내시 균형은 보완 연합의 행동을 주어진 것으로 간주하고, 어떤 연합도 구성원 모두에게 이익이 되는 방식으로 협력적으로 이탈할 수 없는 내시 균형이다.^[19] 그러나 강한 내시 개념은 무제한적인 사적 의사 소통을 허용한다는 점에서 너무 "강하다"고 인식되기도 한다. 실제로 강한 내시 균형은 파레토 효율성을 가져야 한다. 이러한 요구 사항 때문에, 강한 내시는 게임 이론의 많은 분야에서 유용하게 쓰이기에는 너무 드물다.

연합 방지 내시 균형(CPNE)은 참여자들이 소통하고 "자체 시행" 합의를 통해 이탈할 수 있더라도 더 나은 결과를 얻을 수 없을 때를 말한다. 반복적인 엄격한 우월성에 의해 지원되고 파레토 경계에 있는 모든 상관된 전략은 CPNE이다.^[20] CPNE는 코어 이론과 관련이 있다.

내시 균형이 항상 사회적으로 바람직한 결과를 보장하는 것은 아니다. 죄수의 딜레마에서 볼 수 있듯이, 내시 균형은 파레토 최적이 아닐 수 있다.

내시 균형은 순차 게임에서 비합리적인 결과를 초래할 수도 있다. 플레이어들이 실제로 실행하지 않을 위협으로 서로를 "위협"할 수 있기 때문이다. 이러한 게임에서는 부분 게임 완전 내시 균형이 더 의미 있는 분석 도구가 될 수 있다.

부분 게임 완전 내시 균형은 내시 균형의 상위 집합이다. 부분 게임 완전 균형은 내시 균형 외에도 해당 게임의 모든 부분 게임에서 해당 전략이 내시 균형을 이루도록 요구한다. 이는 모든 비현실적 위협을 제거한다. 즉, 상대방이 전략을 변경하도록 하기 위해 비합리적인 움직임을 포함하는 전략은 제거된다.

위 그림은 부분 게임 불완전 내시 균형 문제를 설명하는 간단한 순차 게임을 보여준다. 플레이어 1은 왼쪽(L) 또는 오른쪽(R)을 선택하고, 플레이어 2는 플레이어 1에게 친절(K)하거나 불친절(U)하게 대하도록 요구받는다. 플레이어 2는 플레이어 1이 왼쪽으로 갔을 때만 불친절하게 대함으로써 이익을 얻을 수 있다. 플레이어 1이 오른쪽으로 가면 합리적인 플레이어 2는 해당 부분 게임에서 그에게 친절하게 대할 것이다. 그러나 2(2)에서 불친절하게 굴려는 비현실적 위협은 여전히 파란색 (L, (U,U)) 내시 균형의 일부이다. 따라서 양 당사자가 합리적인 행동을 할 것으로 예상될 수 있다면, 동적 비일관성이 발생할 때 부분 게임 완전 내시 균형이 더 의미있는 해결 개념이 될 수 있다.

안정성 개념은 다양한 종류의 균형 분석에 유용하며, 내시 균형에도 적용될 수 있다. 혼합 전략 게임의 내시 균형은 한 플레이어의 확률에 작은 변화가 발생했을 때 다음 두 가지 조건이 충족되면 안정적이다.

# 변화하지 않은 플레이어는 새로운 상황에서 더 나은 전략을 가지고 있지 않다.

# 변화한 플레이어는 이제 엄격하게 더 나쁜 전략으로 플레이하고 있다.

현실에서는 균형이 쉽게 깨질 수 있다는 문제점도 있다.

8. 결론

내시 균형은 사회 현상을 이해하고 분석하는 데 유용한 도구이지만, 다음과 같은 한계점도 가지고 있다.

• 비합리적인 결과: 내시 균형이 반드시 파레토 최적을 보장하지는 않으며, 순차 게임에서는 비합리적인 결과를 초래할 수 있다. 플레이어들이 실제로 실행하지 않을 위협으로 서로를 "위협"하는 경우가 발생할 수 있기 때문이다.
• 안정성 문제: 협동 게임에서 내시 균형은 충분히 설득력이 없을 수 있다. 강한 내시 균형은 모든 연합의 이탈을 허용하지만, 지나치게 "강한" 조건으로 인해 실제 적용이 어려울 수 있다.
• 존재성 문제: 선택 집합이 무한하고 콤팩트하지 않으면 내시 균형이 존재하지 않을 수 있다. 예를 들어, 두 플레이어가 숫자를 동시에 지정하고 더 큰 숫자를 지정한 플레이어가 승리하는 게임은 내시 균형을 갖지 않는다.

참조

_[1] 서적 A Course in Game Theory MIT 1994-07-12
_[2] 간행물 Nash Equilibrium Palgrave Macmillan 1987
_[3] 논문 Equilibrium points in n-person games
_[4] 서적 The Strategy of Conflict Harvard University Press 1980 # copyright 1960, 1980로 되어있으나, 출판일을 1980으로 통일함.
_[5] 논문 Must Try Harder: Evaluating the Role of Effort in Educational Attainment
_[6] 논문 Game Theory and the Politics of Global Warming: The State of Play and Beyond
_[7] 논문 Risks and benefits of catching pretty good yield in multispecies mixed fisheries
_[8] 웹사이트 Marketing Lessons from Dr. Nash - Andrew Frank http://blogs.gartner[...] 2015-05-25
_[9] 논문 Testing Mixed-Strategy Equilibria when Players Are Heterogeneous: The Case of Penalty Kicks in Soccer http://pricetheory.u[...]
_[10] 논문 Mixed-Strategy Nash Equilibrium for Crowd Navigation 2024
_[11] 논문 A Mean-Field Game of Evacuation in Multilevel Building
_[12] 논문 Mean-Field-Type Games in Engineering 2017-09-27
_[13] 서적 Researches on the Mathematical Principles of the Theory of Wealth
_[14] 서적 Theory of Games and Economic Behavior Princeton University Press
_[15] 논문 On the Existence of Pure Strategy Nash Equilibria in Large Games http://fesrvsd.fe.un[...]
_[16] 웹사이트 Preliminaries of Game Theory http://www.scienceof[...]
_[17] 웹사이트 Nash Equilibria http://hoylab.cornel[...]
_[18] 논문 Coalition-Proof Equilibria I. Concepts
_[19] 서적 Contributions to the Theory of Games Princeton University Press
_[20] 논문 Coalition-Proof Equilibrium http://e-archivo.uc3[...]
_[21] 웹사이트 Lecture 6: Continuous and Discontinuous Games https://ocw.mit.edu/[...] MIT OpenCourseWare
_[22] 논문 Existence and Uniqueness of Equilibrium Points for Concave N-Person Games https://www.jstor.or[...]
_[23] 서적 Game Theory http://www.cdam.lse.[...] Texas A&M University, London School of Economics
_[24] 서적 Learning to Play Cournot Duoploy Strategies http://excen.gsu.edu[...] Texas A&M University, University of Arizona
_[25] 서적 Game Theory MIT Press
_[26] 논문 Computing Equilibria of N-Person Games https://epubs.siam.o[...] 1971-07-01
_[27] 논문 Oddness of the Number of Equilibrium Points: A New Proof https://doi.org/10.1[...] 1973-12-01